package com.company;

import javax.swing.*;
import java.math.BigDecimal;
import java.util.*;

import static java.lang.Math.abs;

/**
 * @author shencaobo
 */
public class Solution {


    public boolean isMatchTwo(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        soutString(dp);
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                soutString(dp);
            }
        }
        soutString(dp);
        return dp[m][n];
    }

    public void soutString(boolean[][] dp) {
        System.out.println(" ");
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + "  ");
            }
            System.out.println(" ");
        }
    }

    public boolean matchString(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean ifFirstMach = s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '?');
        boolean ifAnyMatch = false;
        if (p.charAt(0) == '*') {
            ifAnyMatch = true;
        }
        int i = 1;
        while (p.length() > i) {
            if (p.charAt(i) == '*') {
                i++;
            } else {
                break;
            }
        }
        //单个字符匹配
        if (ifFirstMach) {
            return matchString(s.substring(1), p.substring(1));
        } else if (ifAnyMatch) {
            return matchString(s.substring(1), p) || matchString(s.substring(1), p.substring(1)) || matchString(s, p.substring(i));
        } else {
            return false;
        }

    }


    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int len1 = num1.length();
        int len2 = num2.length();
        int[] ansArr = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = len2 - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                ansArr[i + j + 1] += n1 * n2;
            }
        }
        //循环处理都变成一位
        for (int i = len1 + len2 - 1; i > 0; i--) {
            //最小值
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        StringBuilder sb = new StringBuilder();
        int index = ansArr[0] == 0 ? 1 : 0;
        while (index < len1 + len2) {
            sb.append(ansArr[index]);
            index++;
        }

        return sb.toString();
    }

    public int trap(int[] height) {
        int totalWater = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);

            if (height[left] < height[right]) {
                totalWater += leftMax - height[left];
                ++left;
            } else {
                totalWater += rightMax - height[right];
                --right;
            }


        }
        return totalWater;
        //
        // int ans = 0;
        // int left = 0, right = height.length - 1;
        // int leftMax = 0, rightMax = 0;
        // while (left < right) {
        //     leftMax = Math.max(leftMax, height[left]);
        //     rightMax = Math.max(rightMax, height[right]);
        //     if (height[left] < height[right]) {
        //         ans += leftMax - height[left];
        //         ++left;
        //     } else {
        //         ans += rightMax - height[right];
        //         --right;
        //     }
        // }
        // return ans;

    }


    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0) {
            return 1;
        }
        Arrays.sort(nums);

        int n = 0;
        while (n < nums.length && nums[n] <= 0) {
            n++;
        }
        int min = 1;
        for (int i = 0; (n + i) < nums.length; ++i) {
            if (nums[n + i] == min) {
                ++min;
            }
            if (nums[n + i] > min) {
                return min;
            }
        }
        return min;
    }


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        HashSet listBack = new HashSet();

        Arrays.sort(candidates);
        List<Integer> list = new ArrayList();
        combinationSum2Dfs(candidates, target, listBack, list, candidates.length - 1);
        return new ArrayList<>(listBack);
    }

    public void combinationSum2Dfs(int[] candidates, int target, HashSet listBack, List<Integer> list, int idx) {
        if (target == 0) {
            listBack.add(new ArrayList<>(list));
            return;
        }
        for (int i = idx; i >= 0; i--) {
            if (target - candidates[i] >= 0) {
                //修剪，和上一次一样的就不要了。
                if (i + 1 <= idx && candidates[i] == candidates[i + 1]) {
                    continue;
                }
                list.add(candidates[i]);
                combinationSum2Dfs(candidates, target - candidates[i], listBack, list, i - 1);
                list.remove(list.size() - 1);
            }
        }
    }


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> listBack = new ArrayList();

        Arrays.sort(candidates);
        List<Integer> list = new ArrayList();
        combinationSumDfs(candidates, target, listBack, list, 0);
        return listBack;
    }

    public void combinationSumDfs(int[] candidates, int target, List<List<Integer>> listBack, List<Integer> list, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            listBack.add(new ArrayList<>(list));
            return;
        }
        // 直接跳过
        combinationSumDfs(candidates, target, listBack, list, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {//
            list.add(candidates[idx]);
            combinationSumDfs(candidates, target - candidates[idx], listBack, list, idx);
            list.remove(list.size() - 1);
        }
    }


    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        String x = countAndSay(n - 1);
        int count = 0;
        Character num = x.charAt(0);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < x.length(); ++i) {
            char y = x.charAt(i);
            if (y == num) {
                ++count;
            } else {
                sb.append(count);
                sb.append(num);
                num = y;
                count = 1;
            }
        }
        if (num != null) {
            sb.append(count);
            sb.append(num);
        }

        return sb.toString();
    }


    private int[][] rows = new int[9][9];
    private int[][] cols = new int[9][9];
    private int[][] sbox = new int[9][9];

    private int flag = 0;
    private List<int[]> spaces = new ArrayList<int[]>();

    private boolean solveSudokuFlag = false;

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                //获取第一个数
                char num = board[i][j];
                if (num != '.') {
                    flag++;
                    int n = (int) num - '1';
                    int boxIndex = (i / 3) * 3 + j / 3;
                    rows[i][n] = 1;
                    cols[j][n] = 1;
                    sbox[boxIndex][n] = 1;
                } else {
                    spaces.add(new int[]{i, j});
                }
            }
        }

        solveSudokuDfs(board, 0);

    }


    public void solveSudokuDfs(char[][] board, int spaceNum) {
        if (spaceNum == spaces.size()) {
            solveSudokuFlag = true;
            return;
        }
        int[] space = spaces.get(spaceNum);
        int x = space[0];
        int y = space[1];
        for (int i = 0; i < 9 && flag <= 81; i++) {
            if (rows[x][i] == 0 && cols[y][i] == 0 && sbox[(x / 3) * 3 + y / 3][i] == 0) {
                rows[x][i] = cols[y][i] = sbox[(x / 3) * 3 + y / 3][i] = 1;
                board[x][y] = (char) (i + '1');
                solveSudokuDfs(board, spaceNum + 1);
                rows[x][i] = cols[y][i] = sbox[(x / 3) * 3 + y / 3][i] = 0;
            }
        }
    }

    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] col = new int[9][9];
        int[][] sbox = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                //获取第一个数
                char num = board[i][j];
                if (num != '.') {
                    //转数字特殊方法
                    int n = (int) num - '1';
                    int boxIndex = (i / 3) * 3 + j / 3;
                    if (rows[i][n] == 1 || col[j][n] == 1 || sbox[boxIndex][n] == 1) {
                        return false;
                    }
                    rows[i][n] = 1;
                    col[j][n] = 1;
                    sbox[boxIndex][n] = 1;
                }
            }
        }
        return true;
    }

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        //1.判断特殊情况
        if (right == -1) {
            return 0;
        }
        if (nums[left] >= target) {
            return left;
        }
        if (nums[right] == target) {
            return right;
        }
        if (nums[right] < target) {
            return right + 1;
        }


        //2.循环查找目标位置
        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] == target) {
                return mid;
            }
            if (mid == left || mid == right) {
                break;
            } else if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }


        return left + 1;
    }

    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        //二分查找
        int flag = halfFind(nums, left, right, target);
        left = flag;
        right = flag;
        while (left - 1 > 0) {
            if (nums[left - 1] == target) {
                left--;
            } else {
                break;
            }
        }
        while (right + 1 < nums.length) {
            if (nums[right + 1] == target) {
                right++;
            } else {
                break;
            }
        }
        return new int[]{left, right};
    }


    public int halfFind(int[] nums, int left, int right, int target) {
        //注意边界条件的判断！！！
        if (nums.length == 0) {
            return -1;
        }
        if (nums[left] == target) {
            return left;
        }
        if (nums[right] == target) {
            return right;
        }
        int mid = (left + right) / 2;
        //没匹配到的条件
        if (mid == left || mid == right) {
            return -1;
        }
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return halfFind(nums, left, mid, target);
        } else {
            return halfFind(nums, mid, right, target);
        }
    }

    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            //与第一个判断大小
            if (nums[0] <= nums[mid]) {
                //如果 第一个 比 目标值小，，中间值 比目标值大
                if (nums[0] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target <= nums[n - 1] && nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }


        }
        return -1;
    }


    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> st = new Stack<>();
        st.add(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                //左括号就将坐标加入栈
                st.add(i);
            } else {
                //出栈
                st.pop();
                //如果s栈是空
                if (st.isEmpty()) {
                    //加入当前坐标，就是下一个最长序列组合。
                    st.add(i);
                } else {
                    //max
                    maxans = Math.max(maxans, i - st.peek());
                }
            }
        }
        return maxans;
    }


    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int x = len - 2;
        //先找到x  x是 第一个，增加的序列。
        while (x >= 0 && nums[x] >= nums[x + 1]) {
            x--;
        }
        if (x >= 0) {
            int y = len - 1;
            //找nums[y]第一个比nums[x]大的下标
            while (y >= 0 && nums[x] >= nums[y]) {
                y--;
            }
            //交换
            swap(nums, x, y);
        }
        //逆序操作
        reverse(nums, x + 1);
    }

    //交换
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //逆序
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }


    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        int wordLen = words[0].length();
        //HashMap1 存所有单词
        HashMap<String, Integer> allWords = new HashMap<>();
        for (String w : words) {
            int value = allWords.getOrDefault(w, 0);
            allWords.put(w, value + 1);
        }
        //遍历所有子串
        //剩余总长度要小于，所有单词长度之和
        for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
            //HashMap2 存当前扫描的字符串含有的单词
            HashMap<String, Integer> hasWords = new HashMap<>();
            //判断成功包含的子字符串个数。
            int num = 0;
            //判断该子串是否符合  小于 总的个数
            while (num < wordNum) {
                //截取出一个字符串
                String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                //判断该单词在 HashMap1 中
                if (allWords.containsKey(word)) {
                    int value = hasWords.getOrDefault(word, 0);
                    //增加value
                    hasWords.put(word, value + 1);
                    //判断当前单词的 value 和 HashMap1 中该单词的 value
                    if (hasWords.get(word) > allWords.get(word)) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            //判断是不是所有的单词都符合条件
            if (num == wordNum) {
                res.add(i);
            }
        }
        return res;
    }

    public int divide(int dividend, int divisor) {
        //除数是1直接返回
        if (divisor == 1) {
            return dividend;
        }
        //除数是-1 判断下最小值
        if (divisor == -1) {
            return dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : -dividend;
        }
        //x,y记录符号问题
        int x = dividend < 0 ? -1 : 1;
        int y = divisor < 0 ? -1 : 1;
        //a b 记录新的数据
        long a = dividend;
        long b = divisor;
        a = x == 1 ? a : -a;
        b = y == 1 ? b : -b;
        int num = div(a, b);
        return x == y ? num : -num;
    }

    public int div(long a, long b) {
        if (a < b) {
            return 0;
        }
        int count = 1;
        long tb = b;
        //如果比 双倍大就，翻倍,以双倍的形式算
        while (a >= (tb + tb)) {
            count = count + count;
            tb = tb + tb;
        }

        return count + div(a - tb, b);
    }


    public int strStrKMP(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    public int strStr(String haystack, String needle) {
        int str1Len = haystack.length();
        int str2Len = needle.length();
        //特殊情况判断
        if (needle.isEmpty()) {
            return 0;
        }
        if (haystack.isEmpty()) {
            return -1;
        }
        if (str1Len < str2Len) {
            return -1;
        }
        //left来匹配头，right来匹配needle
        int left = 0;
        int right = 0;
        char first = needle.charAt(0);

        //条件判断，剩余的长度一定要小于 第二个的长度
        for (; left < str1Len - str2Len + 1; left++) {
            if (haystack.charAt(left) == first) {
                //特殊情况，如果2的长度就是1
                if (str2Len == 1) {
                    return left;
                }
                for (right = 1; right < str2Len; right++) {
                    if (haystack.charAt(left + right) != needle.charAt(right)) {
                        break;
                    }
                    if (right == needle.length() - 1) {
                        return left;
                    }
                }
            }
        }
        return -1;
    }


    public int removeElement(int[] nums, int val) {
        //双指针
        int pre = 0;
        //循环当前数组
        int now = 0;
        for (; now < nums.length; now++) {
            //如果前一个和当前不同
            if (nums[now] != val) {
                nums[pre] = nums[now];
                pre++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
        return pre;
    }

    public int removeDuplicates(int[] nums) {
        //双指针
        int pre = 0;
        //循环当前数组
        int now = 1;
        for (; now < nums.length; ++now) {
            //如果前一个和当前不同
            if (nums[pre] != nums[now]) {
                ++pre;
                nums[pre] = nums[now];
            }
        }
        return ++pre;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode preHead = new ListNode(0, head);
        ListNode first = preHead;

        Stack<ListNode> st = new Stack();
        while (head != null) {
            //将交换的数组，放到栈中
            st.add(head);
            if (st.size() == k) {
                //栈里面完成交换，返回
                first = swapNodes(st, first, k);
                head = first;
            }
            head = head.next;
        }
        return preHead.next;
    }

    public ListNode swapNodes(Stack st, ListNode first, int k) {
        ListNode stPop = (ListNode) st.pop();
        first.next = stPop;
        ListNode last = stPop.next;
        while (st.size() > 0) {
            stPop.next = (ListNode) st.pop();
            stPop = stPop.next;
        }
        stPop.next = last;

        return stPop;
    }


    public ListNode swapPairs(ListNode head) {

        if (head == null) {
            return head;
        }
        ListNode preHead = new ListNode(0, head);
        ListNode swapNode = preHead;
        //1、循环链表。
        while (head != null && head.next != null) {
            //2、交换
            swapNode.next = head.next;
            head.next = head.next.next;
            swapNode.next.next = head;
            swapNode = head;
            head = head.next;

        }
        return preHead.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        ListNode head = null;

        for (ListNode node : lists) {
            head = mergeTwoList(head, node);
        }

        return head;
    }

    public ListNode mergeTwoList(ListNode left, ListNode right) {
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        if (left.val < right.val) {
            left.next = mergeTwoList(left.next, right);
            return left;
        } else {
            right.next = mergeTwoList(left, right.next);
            return right;
        }
    }


    public List<String> generateParenthesis(int n) {
        if (n <= 0) {
            return null;
        }


        List<String> list = new ArrayList<>();
        findNext(list, "", n, n);
        return list;

    }

    public void findNext(List<String> list, String parenthesis, int left, int right) {
        if (left == 0 && right == 0) {
            list.add(parenthesis);
        }
        //没有左括号，必须左括号
        if (left == right) {
            parenthesis += "(";
            findNext(list, parenthesis, --left, right);
        } else {
            //有左括号，可以右括号 也可以左括号
            if (left > 0) {
                String leftParenthesis = parenthesis + "(";
                //System.out.println(leftParenthesis + left + " " + right);
                findNext(list, leftParenthesis, left - 1, right);
            }
            if (right > 0) {
                String rightParenthesis = parenthesis + ")";
                //System.out.println(rightParenthesis + left + " " + right);
                findNext(list, rightParenthesis, left, right - 1);
            }
        }
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // //1.判断特殊情况
        // if (l1 == null) {
        //     return l2;
        // } else if (l2 == null) {
        //     return l1;
        // } else if (l1.val < l2.val) {
        //     l1.next = mergeTwoLists(l1.next, l2);
        //     return l1;
        // } else {
        //     l2.next = mergeTwoLists(l1, l2.next);
        //     return l2;
        // }

        //1.判断特殊情况
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        //2.定义结束链表的头结点方便返回。记录next的节点
        ListNode head = new ListNode(0);
        ListNode nextNode = head;
        //3.循环比较两链表的值  合并到一个链表

        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                nextNode.next = l2;
                nextNode = nextNode.next;

                l2 = l2.next;
                if (l2 == null) {
                    nextNode.next = l1;
                }
            } else {
                nextNode.next = l1;
                nextNode = nextNode.next;
                l1 = l1.next;
                if (l1 == null) {
                    nextNode.next = l2;
                }
            }
        }

        return head.next;
    }


    public boolean isValid(String s) {
        //优化 可以用hashMap键值对存 左右括号
        // Map<Character, Character> pairs = new HashMap<Character, Character>() {{
        //     put(')', '(');
        //     put(']', '[');
        //     put('}', '{');
        // }};

        String left = "({[";
        Stack<Character> stack = new Stack();

        for (int i = 0; i < s.length(); i++) {
            Character val = s.charAt(i);
            if (left.contains(val.toString())) {
                stack.add(val);
            } else {
                if (stack.size() == 0) {
                    return false;
                }
                Character stackVal = stack.pop();

                //判断左边等于右边
                if (stackVal == '(' && val != ')') {
                    return false;
                } else if (stackVal == '{' && val != '}') {
                    return false;
                } else if (stackVal == '[' && val != ']') {
                    return false;
                }
            }
        }
        if (stack.size() != 0) {
            return false;
        }
        return true;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preHead = new ListNode(0, head);
        ListNode first = preHead;
        ListNode second = preHead;

        while (n > 0) {
            first = first.next;
            --n;
        }
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return preHead.next;
    }


    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> listArrayList = new ArrayList<>();
        int len = nums.length;
        if (nums == null && len < 4) {
            return null;
        }
        Arrays.sort(nums);
        //第一重循环
        for (int first = 0; first < len - 3; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }

            //未想到  左边四个之和大于他了，直接就可以下一步
            if (nums[first] + nums[first + 1] + nums[first + 2] + nums[first + 3] > target) {
                break;
            }
            //未想到  first + 最右边三个 还小于他，first就可以继续
            if (nums[first] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
                continue;
            }


            //第二重循环
            for (int second = first + 1; second < len - 2; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }

                int sumFirstSecond = nums[first] + nums[second];

                //未想到 一样 左边first + second + 左边两个 直接比他大，不用循环
                if (nums[first] + nums[second] + nums[second + 1] + nums[second + 2] > target) {
                    break;
                }
                //未想到  左边first + second + 最右边两个 直接比他小，不用循环 second++
                if (nums[first] + nums[second] + nums[len - 2] + nums[len - 1] < target) {
                    continue;
                }


                int left = second + 1;
                int right = len - 1;
                //左右 同时往中间循环
                while (left < right) {
                    int sum = sumFirstSecond + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        if (sum == target) {
                            listArrayList.add(Arrays.asList(nums[first], nums[second], nums[left], nums[right]));
                            //关键步骤，去掉重复项
                            while (left < right && nums[left] == nums[left + 1]) {
                                left++;
                            }
                            while (left < right && nums[right] == nums[right - 1]) {
                                right--;
                            }
                            left++;
                            right--;
                        }
                    }
                }
            }
        }
        return listArrayList;


    }


    public List<String> letterCombinations(String digits) {
        //排除为null 和 "" 的情况
        if (digits.equals("") || digits == null) {
            return new ArrayList<>();
        }
        //匹配序列
        HashMap<String, String> map = new HashMap<>();
        map.put("2", "abc");
        map.put("3", "def");
        map.put("4", "ghi");
        map.put("5", "jkl");
        map.put("6", "mno");
        map.put("7", "pqrs");
        map.put("8", "tuv");
        map.put("9", "wxyz");

        //调用递归
        return getCombinationsList(0, digits, map, null);
    }

    /**
     * 递归获取
     */
    public List<String> getCombinationsList(int address, String digits, HashMap<String, String> map, List<String> back) {
        String num = String.valueOf(digits.charAt(address));
        String mapString = map.get(num);

        List<String> combinations = new ArrayList();
        //第一次进来，就直接加
        if (back == null) {
            for (char i : mapString.toCharArray()) {
                combinations.add(String.valueOf(i));
            }
        } else {
            //后面进来就要笛卡尔积
            for (String x : back) {
                for (char i : mapString.toCharArray()) {
                    combinations.add(x.concat(String.valueOf(i)));
                }
            }
        }
        //如果长度就是最后一位了 直接返回数组
        if (address == digits.length() - 1) {
            return combinations;
        } else {
            //如果长度不是最后一位，加加，继续递归
            ++address;
            return getCombinationsList(address, digits, map, combinations);
        }
    }


    //最近的三数之和
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        int total = 1000;
        for (int i = 0; i < len - 2; i++) {
            //去掉重复计算
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //左边第一个
            int j = i + 1;
            //右边最后一个
            int k = len - 1;
            while (j < k) {
                int x = nums[i] + nums[j] + nums[k];

                if (Math.abs(x - target) < Math.abs(total - target)) {
                    total = x;
                }

                if (x - target == 0) {
                    return x;
                } else if (x - target > 0) {
                    int k0 = k - 1;
                    while (j < k0 && nums[k] == nums[k0]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    int j0 = j + 1;
                    while (j0 < k && nums[j] == nums[j0]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return total;
    }


    //三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList();
        //先排序
        Arrays.sort(nums);
        int len = nums.length;
        if (len < 3) {
            return list;
        }
        for (int i = 0; i < len; i++) {
            // 如果当前数字大于0，则三数之和一定大于0，结束
            if (nums[i] > 0) {
                break;
            }
            //连续一样的去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 去重
            }
            int min = i + 1;
            int max = len - 1;
            while (min < max) {
                int sum = nums[i] + nums[min] + nums[max];
                if (sum == 0) {
                    list.add(Arrays.asList(nums[i], nums[min], nums[max]));
//                    List<Integer> l1 = new ArrayList<>();
//                    l1.add(nums[i]);
//                    l1.add(nums[min]);
//                    l1.add(nums[max]);
//                    list.add(l1);
                    while (min < max && nums[min] == nums[min + 1]) {
                        min++; // 去重
                    }
                    while (min < max && nums[max] == nums[max - 1]) {
                        max--; // 去重
                    }
                    min++;
                    max--;
                } else if (sum > 0) {
                    max--;
                } else {
                    min++;
                }
            }
        }
        return list;
    }


    //最长公共前缀   以第一个为模板，匹配逐渐往后、
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String s = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            while (j < s.length() && j < strs[i].length() && s.charAt(j) == strs[i].charAt(j)) {
                j++;
            }
            s = s.substring(0, j);
        }
        return s;
    }

    //罗马数字转整数
    public int romanToInt(String s) {
        Map<String, Integer> map = new HashMap<>();
        map.put("I", 1);
        map.put("IV", 4);
        map.put("V", 5);
        map.put("IX", 9);
        map.put("X", 10);
        map.put("XL", 40);
        map.put("L", 50);
        map.put("XC", 90);
        map.put("C", 100);
        map.put("CD", 400);
        map.put("D", 500);
        map.put("CM", 900);
        map.put("M", 1000);

        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            //没有超出长度，且匹配到了。
            if (i + 1 < s.length() && map.containsKey(s.substring(i, i + 2))) {
                num += map.get(s.substring(i, i + 2));
                i++;
            } else {
                num += map.get(s.substring(i, i + 1));
            }
        }
        return num;
    }


    //整数转罗马数字
    public String intToRoman(int num) {

        if (num < 1 || num > 3999) {
            return null;
        }
        String[] thousands = {"", "M", "MM", "MMM"};
        String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

        return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
    }


    //盛最多水的容器
    public int maxArea(int[] height) {
        int max = 0;
        int i = 0;
        int j = height.length - 1;
        while (i < j) {
            int area = (j - i) * Math.min(height[i], height[j]);
            if (height[i] > height[j]) {
                j--;
            } else {
                i++;
            }
            max = Math.max(max, area);
        }
        return max;
    }


    //正则表达式匹配  截取字符串递归，其实应该用动态规划 更好
    public boolean isMatch(String s, String p) {
        return isMatchSing(s, p);
    }

    //截取字符串 递归的形式来做
    public boolean isMatchSing(String s, String p) {
        //首先判断 空的情况
        if (p.isEmpty()) {
            return s.isEmpty();
        }

        //检查首字母是否匹配
        boolean isFirstMath = s.length() > 0 && (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0));

        //检查模式串的下个字符是否为 *
        boolean isMatchAny = p.length() > 1 && p.charAt(1) == '*';
        if (isMatchAny) {
            //如果下一个字符为 * 则第一个字符就不重要了
            //如果包含"*"，可以忽略掉（当前字符*）
            //也可以忽略掉字符串中的当前字符(如果能匹配上)
            return isMatchSing(s, p.substring(2)) || (isFirstMath && isMatchSing(s.substring(1), p));
        } else {
            //单个字符匹配的情况
            return isFirstMath && isMatchSing(s.substring(1), p.substring(1));
        }
    }

    //回文数
    //    给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
    //    回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        } else {
            int y = 0;
            while (x > y) {
                y = y * 10 + x % 10;
                x = x / 10;
            }
            return x == y || x == y / 10;
        }


        //取巧法。用了翻转数字。
        //        if (x < 0)
        //            return false;
        //        else {
        //            return reverse(x) == x;
        //        }
    }


    // 字符串转换整数 (atoi)  其实最好用 有限自动机来实现
    public int myAtoi(String s) {
        s = s.trim();
        if (s.length() == 0) {
            return 0;
        }
        long num = 0L;

        if (!Character.isDigit(s.charAt(0))
                && s.charAt(0) != '-' && s.charAt(0) != '+') {
            return 0;
        }

        boolean posNum = s.charAt(0) != '-';

        for (int i = !Character.isDigit(s.charAt(0)) ? 1 : 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int last;
                if (posNum) {
                    last = c - '0';
                } else {
                    last = -(c - '0');
                }
                if (num > Integer.MAX_VALUE / 10 || (num == Integer.MAX_VALUE / 10 && last > 7)) {
                    return 2147483647;
                }
                if (num < Integer.MIN_VALUE / 10 || (num == Integer.MIN_VALUE / 10 && last < -8)) {
                    return -2147483648;
                }

                num = num * 10 + last;
            } else {
                return (int) num;
            }
        }
        return (int) num;
    }


    //整数反转   给你一个 32 位的有符号整数 x ，返回 x 中每位上的数字反转后的结果。
    //    输入：x = 123
    //    输出：321
    public int reverse(int x) {
        int num = 0;
        while (x != 0) {
            int last = x % 10;
            if (num > Integer.MAX_VALUE / 10 || (num == Integer.MAX_VALUE / 10 && last > 7)) {
                return 0;
            }
            if (num < Integer.MIN_VALUE / 10 || (num == Integer.MIN_VALUE / 10 && last < -8)) {
                return 0;
            }

            num = num * 10 + last;
            x = x / 10;
        }
        return num;
    }

    //    Z 字形变换
    //    输入：s = "PAYPALISHIRING", numRows = 4
    //    输出："PINALSIGYAHRPI"
    //    解释：
    //    P     I    N
    //    A   L S  I G
    //    Y A   H R
    //    P     I
    public String convert(String s, int numRows) {
        StringBuilder str = new StringBuilder();
        int totalLen = s.length();
        if (totalLen == 0) {
            return "";
        }
        if (numRows == 1) {
            return s;
        }
        int baseInt = 2 * numRows - 2;
        for (int i = 0; i < numRows; i++) {
            if (i < totalLen) {
                str.append(s.charAt(i));
            }
            int j = 1;
            boolean leftBol = true, rightBol = true;
            while (leftBol || rightBol) {
                int left = i + j * baseInt - 2 * i;
                int right = i + j * baseInt;
                //判断左边 left
                if (leftBol && i != 0 && i != numRows - 1 && left < totalLen) {
                    str.append(s.charAt(left));
                } else {
                    leftBol = false;
                }

                //判断右边 right
                if (rightBol && right < totalLen) {
                    str.append(s.charAt(right));
                } else {
                    rightBol = false;
                }
                j++;
            }
        }
        return str.toString();
    }


    //最长回文子串 给你一个字符串 s，找到 s 中最长的回文子串。 动态规划   ，解题思路，定位中间，往两边拓展，算臂长，最后来截取字符串。
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int max = 1;
        int strLen = 0;
        //先考虑第一位的情况
        if (s.length() > 1 && s.charAt(0) == s.charAt(1)) {
            max++;
        }
        //循环字符串依次作为 中心，往两边拓展
        for (int i = 1; i < s.length(); i++) {
            //关键算法，算最长的串
            int a = getLongestPalindrome(s, i);
            if (max < a) {
                max = a;
                strLen = i;
            }
        }
        int half = max / 2;
        if (max % 2 == 1) {
            return s.substring(strLen - half, strLen - half + max);
        } else {
            return s.substring(strLen - half + 1, strLen - half + 1 + max);
        }

    }

    private int getLongestPalindrome(String s, int i) {
        int count1 = 1;
        int count2 = 1;
        int y = 1;
        // 中心为单个的 回文串
        while (i - y >= 0 && i + y < s.length()) {
            if (s.charAt(i - y) == s.charAt(i + y)) {
                count1 += 2;
            } else {
                break;
            }
            y++;
        }
        y = 1;
        boolean flag = true;
        //中心为偶数的回文串。
        while (i - y + 1 >= 0 && i + y < s.length()) {
            if (s.charAt(i) == s.charAt(i + y) && flag) {
                count2++;
                flag = false;
            } else if (s.charAt(i - y + 1) == s.charAt(i + y)) {
                count2 += 2;
            } else {
                break;
            }
            y++;

        }
        return Math.max(count1, count2);
    }

    public String longestPalindromeTwo(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        soutString(dp);
        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
                soutString(dp);
            }
        }
        return s.substring(begin, begin + maxLen);
    }


    //寻找两个正序数组的中位数  二分查找  有难度的。
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //中长度
        int total = nums1.length + nums2.length;
        if (total % 2 == 1) {
            int mid = total / 2;
            return getKthElement(nums1, nums2, mid + 1);
        } else {
            int mid = total / 2 - 1;
            return (getKthElement(nums1, nums2, mid + 1) + getKthElement(nums1, nums2, mid + 2)) / 2;
        }
    }

    //  k 需要查找的第几个，总共5个，查的是，第三个传入3，但是数组下标为2.
    private double getKthElement(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length, len2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kth = 0;
        while (true) {
            //先考虑边界
            if (len1 == index1) {
                return nums2[index2 + k - 1];
            }
            if (len2 == index2) {
                return nums1[index2 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            //正常情况
            int half = k / 2;
            //对半查
            int newIndex1 = Math.min(index1 + half, len1) - 1;
            int newIndex2 = Math.min(index2 + half, len2) - 1;
            //分别取到两个数
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            // 比较
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }

        }

    }


    //最长子串  "abcabcbb" 返回3
    public int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<>();
        int n = s.length();
        if (s.equals("")) {
            return 0;
        } else {
            int max = 0;
            int y = -1;
            for (int i = 0; i < n; i++) {
                if (i != 0) {
                    occ.remove(s.charAt(i - 1));
                }

                for (; y + 1 < n; y++) {
                    if (!occ.contains(s.charAt(y + 1))) {
                        occ.add(s.charAt(y + 1));
                    } else {
                        break;
                    }
                }
                max = Math.max(max, y - i + 1);
            }
            return max;
        }

    }

    //两数相加
    //    输入：l1 = [2,4,3], l2 = [5,6,4]
    //    输出：[7,0,8]
    //    解释：342 + 465 = 807.
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int add = 0;
        ListNode one = l1;
        ListNode two = l2;
        ListNode three = null;
        ListNode five = null;
        while (true) {
            if (one == null && two == null && add == 0) {
                break;
            }
            int a = 0, b = 0;
            if (one != null) {
                a = one.val;
                one = one.next;
            }
            if (two != null) {
                b = two.val;
                two = two.next;
            }
            int total = a + b + add;
            add = total / 10;
            ListNode four = new ListNode(total % 10);
            if (five == null) {
                three = four;
                five = three;
            } else {
                five.next = four;
                five = five.next;
            }
        }
        return three;
    }


    //两数之和
    //    int[] test = {2, 7, 11, 15};
    //    int[] a= Solution.twoSum(test, 9);
    //    System.out.print(a[0]+"    "+a[1]);
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int[] need = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            need[i] = target - nums[i];
            if (i >= 1) {
                for (int y = 0; y < i; y++) {
                    if (nums[i] == need[y]) {
                        res[0] = i;
                        res[1] = y;
                        return res;
                    }
                }
            }
        }
        return res;
    }


}